#include <stdio.h>
#include <stdlib.h>//Don't forget to call free()!!!!!!!
void CutIn(int in,int n,int *p);
void AsSorting(int *p,int n);
void main()
{
    int i,n,cutin;
    int *p;
    printf("please tell me how many numbers you want to input:");
    scanf("%d",&n);
    p=(int *)malloc((n+1)*sizeof(int));
    printf("      input the number array:\n\n");
    for(i=0;i<n;i++)
    {
        printf("please input the No.%d number:",i+1);
        scanf("%d",p+i);
    }
    putchar('\n');
    AsSorting(p,n);
    printf("     After sorting:\n\n");
    for(i=0;i<n;i++)
    {
        printf("%d  ",*(p+i));
    }
    putchar('\n');
    printf("please input the number that you want to insert:");
    scanf("%d",&cutin);
    putchar('\n');
    CutIn(cutin,n,p);
    printf("      The Last Result:\n\n");
    for(i=0;i<n+1;i++)
    {
        printf("%d  ",*(p+i));
    }
    putchar('\n');
    free(p);
}
void AsSorting(int *p,int n)
{
    int i,j,temp;
    for(i=0;i<n;i++)
    {
        for(j=i;j<n;j++)
        {
            if(*(p+i)>*(p+j))
            {
                temp=*(p+i);
                *(p+i)=*(p+j);
                *(p+j)=temp;
            }
        }
    }
}
void CutIn(int in,int n,int *p)
{
    int i,j,k,temp;
    int key;
    for(i=0;i<n;i++)
    {
        if(*(p)>in)
        {
            key=1;
            break;
        }
        if(*(p+i)<=in&&*(p+i+1)>=in)
        {
            key=2;
            k=i+1;
            break;
        }
        if(*(p+n-1)<in)
        {
            key=3;
            break;
        }
    }
    switch(key)
    {
        case 1:
        {
            for(j=n;j>0;j--)
            {
                *(p+j)=*(p+j-1);
            }
            *(p)=in;
            break;
        }
        case 2:
        {
            for(j=n;j>k;j--)
            {
                *(p+j)=*(p+j-1);
            }
            *(p+k)=in;
            break;
        }
        case 3:
        {
            *(p+n)=in;
            break;
        }
    }
}
